package com.sheng.leetcode.year2023.month07.day10;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2023/07/10
 * <p>
 * 16. 最接近的三数之和<p>
 * <p>
 * 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。<p>
 * 请你从 nums 中选出三个整数，使它们的和与 target 最接近。<p>
 * 返回这三个数的和。<p>
 * 假定每组输入只存在恰好一个解。<p>
 * <p>
 * 示例 1：<p>
 * 输入：nums = [-1,2,1,-4], target = 1<p>
 * 输出：2<p>
 * 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：nums = [0,0,0], target = 1<p>
 * 输出：0<p>
 * <p>
 * 提示：<p>
 * 3 <= nums.length <= 1000<p>
 * -1000 <= nums[i] <= 1000<p>
 * -10^4 <= target <= 10^4<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/3sum-closest">16. 最接近的三数之和</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode0016 {

    @Test
    public void test01() {
//        int[] nums = {-1, 2, 1, -4};
//        int target = 1;
//        int[] nums = {0, 0, 0};
//        int target = 1;
        int[] nums = {1, 1, 1, 0};
        int target = 100;
        System.out.println(new Solution().threeSumClosest(nums, target));
    }
}

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int n = nums.length;
        // 排序
        Arrays.sort(nums);
        long ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            // 双指针
            int j = i + 1, k = n - 1;
            while (j < k) {
                // 求出 3 个数的和
                long sum = nums[i] + nums[j] + nums[k];
                if (sum == target) {
                    // 相等时直接返回
                    return target;
                } else if (sum > target) {
                    if (ans > target) {
                        // 两个数都大于 target 时，存小的那个
                        ans = Math.min(sum, ans);
                    } else {
                        if (sum - target < target - ans) {
                            ans = sum;
                        }
                    }
                    k--;
                } else {
                    if (ans > target) {
                        if (ans - target > target - sum) {
                            ans = sum;
                        }
                    } else {
                        // 两个数都小余 target 时，存大的
                        ans = Math.max(ans, sum);
                    }
                    j++;
                }
            }
        }
        return (int) ans;
    }
}
